package com.example.leetcode.prcatice;

/**
 * 给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *
 * <p>可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * <p>
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lMSNwu 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class OfferII25 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode reverseL1 = reverse(l1);
        ListNode reverseL2 = reverse(l2);   //先把两个链表反转
        ListNode head = null ;
        ListNode tail = null;
        int jinZhi = 0;
        while (reverseL1 != null || reverseL2 !=null){
            int l1Value = reverseL1==null? 0: reverseL1.val;
            int l2Value = reverseL2==null? 0: reverseL2.val;
            int sum = l1Value+l2Value + jinZhi;
            // 处理头节点
            if (head == null){
                head =tail = new ListNode(sum % 10);
            }else {
                tail.next = new ListNode(sum %10);
                tail = tail.next;
            }
            jinZhi = sum /10;
            if (reverseL1 != null){
                reverseL1 = reverseL1.next;
            }
            if (reverseL2 != null){
                reverseL2 = reverseL2.next;
            }
        }
        if (jinZhi>0){
            tail.next = new ListNode(jinZhi);
        }
        return reverse(head);
    }

    public ListNode reverse(ListNode listNode){
        ListNode pre = null;
        ListNode now = listNode;
        while (now != null){
            ListNode next = now.next;
            now.next = pre;
            pre = now;
            now = next;
        }
        return pre;
    }
}


class DemoOfferII25{
  public static void main(String[] args) {
    ListNode l1 = new ListNode(7);
    l1.next = new ListNode(2);
    l1.next.next = new ListNode(4);
    l1.next.next.next = new ListNode(3);
    ListNode l2 = new ListNode(5);
    l2.next = new ListNode(6);
    l2.next.next = new ListNode(4);
    OfferII25 o = new OfferII25();
    ListNode listNode = o.addTwoNumbers(l1, l2);
    while (listNode != null){
      System.out.println("val="+listNode.val);
      listNode = listNode.next;
    }
  }
}